1. Field of the Invention
The invention relates in general to algorithms for generating a global placement plan for an integrated circuit, and in particular to an analytical placement algorithm that takes into account preplaced blocks, white space and legalization constraints.
2. Description of Related Art
An integrated circuit (IC) designer typically generates a text-based netlist describing an IC as a hierarchy of modules formed by instances of various components (cells) interconnected by signal paths (nets). The nets are formed by conductors residing on various horizontal layers of the IC and by conductive “vias” passing vertically between layers. Longer nets may include buffers when needed for amplifying signals they convey. A netlist is typically hierarchical in nature with cell instances being organized into low level modules and lower level modules being organized into higher level modules. Most cell instances are usually of standard height but varying width, however some cell instances may be large “intellectual property” (IP) modules implementing devices such as memories and microprocessors.
After creating the netlist, the designer employs a computer-aided placement and routing (P&R) tool to produce a global placement plan indicating a position for each cell instance, and to then produce a routing plan describing the routes and positions of conductors, vias and buffers forming the nets that connect the cell instances. When unable to develop a suitable routing plan, the P&R tool will modify the global placement plan and again attempt to develop a suitable routing plan.
Cell instances of standard height are normally aligned in non-overlapping positions in parallel rows. A cell instance is considered to be in a “legal position” if it is properly aligned in one of the rows. Global placement algorithms typically position cells to optimize routability, but they do not concern themselves with placing cells in legal positions and may allow some cell instances to overlap with each other. Therefore after producing a global placement plan, a P&R tool will “legalize” a global placement plan prior to generating a routing plan by moving cell instances to nearby legal positions. The P&R tool then adjusts the legalized placement plan to produce a detailed placement plan by swapping and shifting cell instance positions to reduce the lengths of nets needed to interconnect the cells and the congestion in any area. The P&R tool finally generates a routing plan based on the detailed placement plan.
The ability of a P&R tool to quickly generate a suitable layout depends largely on how well the global placement plan anticipates the routing requirements. When generating a global placement plan, a typical P&R tool will try to position highly-interconnected cell instances close to one another in order to reduce the total length of the nets (the “wirelength”) needed to interconnect cell instances, but will also try to distribute the cells in a way that allows sufficient space for routing nets between cells. Thus a global placement plan should provide an adequate balance between positioning cell instances close to one another to reduce wirelength and positioning cell instances farther apart to distribute adequate space throughout the placement area for routing nets. Some P&R tools establish an objective (or “cost”) function having cell instance coordinates as independent variables to quantify the routability of a global placement plan. The global placement plan for which the value of the objective function is lowest is considered most likely to be routable. A P&R tool may employ analytical placement algorithms to iteratively adjust the global placement plan, with the algorithm analyzing the global placement plan and the objective function after each iteration to determine how to reposition cells so as to improve the routability of the placement as indicated by the value of the objective function.
Objective functions typically include a term that increases with the estimated total wirelength because routing becomes more difficult as wirelengths increase. Since a global placement plan can also be unroutable even when wirelengths are short when the plan requires too many nets to pass through the same area of an IC, some “congestion-aware” analytical global placement plans add a routing congestion term to the objective function. A congestion aware placement algorithm divides an IC's placement area into regions and places cells within each region. A routing congestion term can be designed to increase the objective function value as the number of nets that must cross any region boundary increases, thereby discouraging the placement algorithm from generating a global placement plan resulting in excessive routing congestion in any region.
Since during the routing stage of the layout process, a P&R tool may have to add buffers as certain points within the layout to amplify signals passing over the longer nets, a global placement plan should distribute empty space (“white space”) throughout the IC in order to accommodate buffers added to the layout during the routing phase. Although a congestion aware placement algorithm tends to distribute white space by spreading cell instances apart, it can still pack some regions too tightly to provide adequate white space for buffer insertions when no routing congestion occurs at the boundaries of those regions.
It is often necessary to place certain cell instances, such as analog blocks, memory blocks, and I/O buffers, in predetermined locations within an IC. Since such “preplaced blocks” act as constraints on positioning cell instances, including preplaced blocks in an IC design makes it more difficult for a placer to find a routable placement, particularly when preplaced blocks are large and numerous. Cells instances of widely varying size and shape can also make placement more difficult.
One drawback to prior art analytical global placement algorithms is that, while the global placement plans are produced with optimized routability as indicated by the objective function, such global placement plans may not be optimal after legalization since a legalization algorithm does not consider the objective function when repositioning cell instances to legal positions. Thus what is needed is an analytical placement algorithm to produce a global placement plan for mixed-size cell instances that optimizes post-legalization routability by minimizing total wirelength while taking into account preplaced block, white space and legalization constraints.